\documentclass[a4paper, 12pt]{mwart}

% \usepackage{a4wide}
\usepackage[hmargin=2cm,vmargin=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[OT4]{fontenc}
\usepackage{polski}
%\usepackage[english,polish]{babel}
\usepackage{graphicx}
%\usepackage{graphics}
\usepackage{indentfirst}
\usepackage{amsmath}
\renewcommand{\baselinestretch}{1.5}
\begin{document}
\thispagestyle{empty}
\noindent
\hfill Wrocław, dn.\ \today

\vspace{1cm}
\begin{center}
  \begin{Large}
   Analiza testowalności uszkodzeń typu opóźnienie ścieżki w zmodyfikowanej sieci sortującej Batchera.\\
  \end{Large}
    projekt w ramach przedmiotu ,,Systemy tolerujące uszkodzenia''
\end{center}

\begin{center}
  Rok akad. 2007/2008, kierunek: INF
\end{center}
\vspace{0.2ex}
\begin{flushright}
\begin{minipage}[t]{0.4\columnwidth}
\noindent
PROWADZĄCY:\\
dr inż.~Piotr Patronik
\end{minipage}
\end{flushright}
\vfill
\noindent
\begin{minipage}[c]{0.9\columnwidth}
Autorzy:\\
  Przemysław Szczepaniak,~140143\\
  Patryk Szymczak,~140149
\end{minipage}

\newpage
\tableofcontents
\newpage
\listoffigures
%\newpage
\listoftables

\newpage
\section{Cel projektu}
\label{sec:cel-projektu}
Celem niniejszej pracy jest przygotowanie implementacji sieci sortującej nieparzysto-parzystej Batchera uwzględniającej modyfikację (opisaną w pracy \cite{PATRONIK}) oraz zbadanie testowalności układu pod kątem błędu opóźnienia ścieżki.

% oraz algorytm modyfikacji tej sieci wg dostępnej literatury. Następnie należy zbadać rozkład i liczbę ścieżek w tak zmodyfikowanej sieci sortującej.

\section{Przegląd zagadnień}
\label{sec:przeglad-zagnien}
\subsection{Uszkodzenie typu opóźnienie}
Uszkodzenie typu \emph{opóźnienie} (ang. delay fault), w przeciwieństwie do uszkodzenia typu sklejenie lub zmostkowanie, nie powoduje zmiany funkcji logicznej realizowanej przez układ. W przypadku jego wystąpienia, zmienia się jedynie czas generowania wartości funkcji. Uszkodzenia typu opóźnienie są jedynym modelem uszkodzeń rozpatrywanych w niniejszej pracy, a ich dokładny i wyczerpujący opis zostanie podany w dalszej części rozdziału.

\subsection{Sieci sortujące}
Sieci sortujące są sprzętową implementacją algorytmów sortowania działających bez pamięci, zbudowanych z powtarzalnych elementów – komparatorów. W ogólnym przypadku, sieć sortująca sortuje dowolne elementy porównywalne i jest zbudowana wyłącznie z komparatorów, elementów o złożoności dostosowanej do złożoności sortowanych elementów. Sieci sortujące implementują algorytmy, których przebieg
jest niezależny od zadanych wartości wejściowych.

\subsection{Sieć scalająca Batchera}
Sieć scalająca nieparzysto-parzysta Batchera o rozmiarze $n$ przyjmuje jako parametry dwa posortowane ciągi, o rozmiarach $\lceil {n \over 2} \rceil$ i $\lfloor {n \over 2} \rfloor$. 
Wynikiem działania sieci scalajacej jest posortowany ciąg o rozmiarze $n$.
Sieć scalająca ma budowę rekurencyjną, sieć o romiarze $n$ składa się z pewnej liczby komparatorów i 2 sieci scalających o rozmiarze $n \over 2$.
Metoda tworzenia sieci scalającej jest następująca:\\
\emph{Jeśli $n > 2$}:
\begin{enumerate}	
	\item Zbuduj dwie sieci scalające o rozmiarze $n/2$ dla linii parzystych $a_0,a_2, \ldots, a_{n-2}$ i nieparzystych $a_1,a_3, \ldots, a_{n-1}$.
	\item Połącz komparatorami linie $a_i$ i  $a_{i+1}$ dla każdego $i$ pochodzacego ze zbioru \\$\{1, 3, 5, 7, \ldots, n-3\}$.
\end{enumerate}
\emph{Jeśli $n = 2$}:
\begin{enumerate}	
	\item Połącz komparatorami linie $a_0$ i $a_1$.
\end{enumerate}

\subsection{Sieć sortująca Batchera}
Sieci sortujące nieparzysto-parzyste Batchera tworzone są poprzez rekurencyjne łączenie nieparzysto-parzystych sieci scalających Batchera. 
Metoda tworzenia sieci sortującej jest następująca:\\
\emph{Jeśli $n > 1$}:
\begin{enumerate}	
	\item Zbuduj sieci sortujące o rozmiarze $n/2$ rekurencyjnie dla linii $a_0, \ldots, a_{n/2-1}$ i $a_{n/2}, \ldots, a_{n-1}$.
	\item Zbuduj sieć scalającą o rozmiarze $n$ i połącz ze zbudowanymi w poprzednim punkcie sieciami sortującymi.
\end{enumerate}

\subsection{Zmodyfikowana sieć scalająca}
Sieci scalające nieparzysto-parzyste Batchera nie posiadają własności silnej testowalności uszkodzeń typu opóźnienie ścieżki. 
Implikuje to identyczną cechę w sieciach sortujących Batchera. Wykazano jednak \cite{PATRONIK}, że wielowyjściowy układ progowy zrealizowany jako całkowicie rozgałęziony jest silnie testowalny, jeżeli sieci łączące mają własność pojedynczej ścieżki sieci łączących. Okazuje się, że istnieje modyfikacja sieci scalającej Batchera OE powodująca nabycie tej własności, a przy tym nie zwiększająca istotnie złożoności sieci (\ref{sec:siec-zmodyfikowana}). 

Zaimplementowaliśmy i zbadaliśmy algorytm modyfikacji dla sieci scalającej o parzystej liczbie linii, z redukcją i bez. 

\section{Implementacja oprogramowania}
\label{sec:opis-szczegolowy-implementacji}
  W celu przeprowadzenia syntezy układów i ich późniejszej analizy, konieczne było napisanie dedykowanego oprogramowania. Implementacja odbyła się w języku \emph{Python}. Program składa się z czterech modułów realizujących różne funkcje:
    \begin{itemize}
     \item logic.py - mechanizmy symulacji układów logicznych,
     \item comparators.py - mechanizm generowania komparatorów,
     \item generator.py - mechanizm generowania sieci Batchera,
     \item analyzer.py - algorytm analizowania złożoności dowolnych układów cyfrowych.
    \end{itemize}

\subsection{Moduł logiki}
\label{sec:modul-logiki}
Ze wzgledu na ścisłe powiązanie generatora i systemu analizy nie było potrzeby tworzenia mechanizmu serializacji generowanych układów. 
Istnieje możliwość wykorzystania mechanizmów języka \emph{Python} w celu serializacji wygenerowanego układu (moduł \emph{pickle}), jednak sprawdza się on tylko dla mniejszych układów, w pozostałych przypadkach poziom 
rekurencji i powiązań między obiektami przerasta możliwości modułu \emph{pickle}.

Jednobitowe sieci sortujące Batchera składają się wyłącznie z bramek \texttt{AND} oraz \texttt{OR}. Stworzyliśmy więc klasę \texttt{Gate}, reprezentuje
ona najmniejszy, niepodzielny element budowanego układu. Po klasie \texttt{Gate} dziedziczą klasy \texttt{AndGate} i \texttt{OrGate} zawierające dodatkowo implementacje logiki
działania obu bramek. Instancje klasy \texttt{Gate} mogą posiadać dowolną liczbę wejść i wyjść. 


Kolejnym elementem wchodzącym w skład modułu jest klasa \texttt{Connection}, reprezentująca połączenia pomiędzy bramkami. 
Każda instancja klasy \texttt{Connection} posiada wejście (\emph{Input}) i wyjście (\emph{Output}), które może zostać przypisane do istniejącej
bramki, bądz innej instancji klasy \texttt{Connection} (upraszcza to generacje układów, komplikując analizę układu. Istnieje jednak możliwość redukcji nadmiarowych instancji). Dodatkowo, połączenie może realizować funkcję negacji przekazywanej wartości, efektywnie zmieniając połączenie w instancje bramki \texttt{NOT}. Ta funkcjonalność nie jest wykorzystywana przy tworzeniu sieci Batchera.

Dodatkową klasą, dziedziczącą po \texttt{Gate}, jest klasa \texttt{Multioutput}. Jest to bramka posiadająca jedno wejście, którego wartość jest propagowane
na wyjścia bramki. Jest to element pozwalający na znaczne uproszczenie mechanizmu generującego układ. Instancje tej klasy mogą w łatwy sposób zostać 
wyeliminowane z wygenerowanego układu, znacznie upraszczając jego analizę.

Klasami integrującymi stworzone bramki i połączenia są klasy \texttt{Circuit} i \texttt{IOCircuit} (rozszerzona wersja, posiadająca możliwość dodania połączeń wejściowych i wyjściowych).
Instancje tych klas mogą zostawać zagnieżdzone w innych instancjach tej samej klasy, co pozwala na modularną generacje układu. 
Klasa \texttt{IOCircuit} zawiera w sobie metody odpowiadające za redukcje nadmiarowych połączeń i instancji \texttt{Multioutput}.

Moduł logiki został napisany bardzo elastycznie, dzięki czemu może być z łatwością rozszerzony lub wykorzystany w innym projekcie. Stanowi de facto, gotową do użycia bibliotekę logiki cyfrowej dla języka Python.

\subsection{Moduł komparatorów}
\label{sec:modul-komparatorow}
Moduł zawiera jedną klasę, \texttt{BitCmpCircuit}, implementuje ona jednobitowy komparator składający się z jednej bramki \texttt{OR} i \texttt{AND}.

\subsection{Moduł generatora}
Generator ma za zadanie tworzenie sieci sortujących i scalających Batchera oraz wprowadzania do nich modyfikacji, dzięki którym układy staną się silnie testowalne.
Za generacje sieci scalających odpowiada metoda \emph{generateOddEvenMerge}, wymaga podania następujących parametrów: rozmiaru sieci oraz klasy komparatora.
Na wyjściu zwracana jest instancja klasy \texttt{IOCircuit}, opisująca wygenerowany układ cyfrowy. 

Sieć jest generowane rekurencyjnie, za pomocą metody \emph{\_\_generateOddEvenMergeRec}, która:
\begin{enumerate}
     \item tworzy nowy układ scalający o zadanym rozmiarze,
     \item podłącza jego wyjścia do zadanych wejść,
     \item dzieli wejścia układu na parzyste i nieparzyste,
     \item metoda jest powtarzana rekurencyjnie dla wejść parzystych i rozmiaru o połowę mniejszego,
     \item metoda jest powtarzana rekurencyjnie dla wejść nieparzystych i rozmiaru o połowę mniejszego.
\end{enumerate}
Powyższy opis jest tylko prawdziwy dla sieci, których rozmiar jest potęgą liczby $2$. 
Sieci o rozmiarze parzystym i nieparzystym posiadają swoje dodatkowe modyfikacje algorytmu, zostały one opisane w pracy dr. Piotra Patronika \cite{PATRONIK}. 

Modyfikację sieci można przeprowadzić za pomocą metody \emph{modify}, przyjmuje ona następujące parametry:
\begin{itemize}
     \item sieć do modyfikacji,
     \item rozmiar sieci,
     \item wartość True/False, jeśli True to zostanie użyty algorytm modyfikacji z redukcją.
\end{itemize}
Metoda zadziała wyłącznie dla sieci scalającej o rozmiarze parzystym.

Za generacje sieci sortującej odpowiada metoda \emph{generateOddEvenSort}, wymaga ona podania następujących parametrów:
\begin{itemize}
     \item rozmiar sieci,
     \item klasa komparatora,
     \item True/False, jeśli True wtedy sieci scalające zostaną poddane modyfikacji,
     \item True/False, jeśli True wtedy sieci scalające zostaną poddane modyfikacji z redukcją.
\end{itemize}
Niestety, redukcja działa wyłącznie dla sieci o rozmiarze, który jest potęgą liczby $2$. Dzieje się tak, ponieważ
sieć o dowolnym innym rozmiarze może zawierać w sobie sieć scalającą o nieparzystym rozmiarze (dla której nie posiadamy
zaimplementowanego algorytmu modyfikacji).

\subsection{Moduł analizatora}
Analizator jest odpowiedzialny za wczytanie opisu układu, zbadanie jego właściwości oraz wyświetlenie zdobytych informacji.
\smallskip\\
Analiza odbywa się przez przejście rekurencyjne przez każde połączenie między dwoma dowolnymi elementami układu od wejścia pierwotnego do wyjścia pierwotnego. W ten sposób możliwe jest otrzymanie różnych informacji charakteryzujących badany układ logiczny:
    \begin{itemize}
     \item liczba bramek poszczególnych typów,
     \item liczba wejść/wyjść pierwotnych,
     \item liczba połączeń,
     \item liczba ścieżek,
     \item długość najkrótszej ścieżki,
     \item długość najdłuższej ścieżki,
     \item średnia długość ścieżki.
    \end{itemize}
Lista możliwości do przeanalizowania nie jest kompletna. Oprogramowanie badawcze może zostać rozwinięte w celu zdobycia innych informacji takich jak np. średnia ilość wyjść z bramki.
\smallskip\\
Warto zauważyć, że podobnie jak biblioteka przechowywania zapisu układów cyfrowych \ref{sec:modul-logiki} jest uniwersalna, również za pomocą analizatora można zbadać \textbf{każdy} logiczny układ cyfrowy o dowolnej liczbie wejść i wyjść pierwotnych.


\newpage
\section{Wyniki syntezy układów}
\label{sec:wyniki-syntezy}
\subsection{Sieć sortująca nieparzysto-parzysta Batchera}
Implementacja algorytmu sieci sortującej Batchera służyła przeprowadzeniu doświadczeń mających na celu zbadanie cech takich sieci.
Pomiary odbyły się w zależności od liczby linii i typu sieci batchera (bez modyfikacji - z modyfikacją). \\
Sieć działa dla dowolnych liczb (zarówno parzystych, jak i nieparzystych).

\subsubsection{Analiza rozkładu ścieżek}
Poniżej znajdują się przykładowe wykresy, obrazujące rozkład ścieżek wewnątrz układu, wygenerowane z użyciem komparatora 1-bitowego, opisanego w rozdziale \ref{sec:modul-komparatorow}.
Charakterystyczną cechą sieci sortujących jest mniejsza liczba ścieżek dla liczby linii będącą potęgą liczby 2. Dla zwiększenia czytelności, wykres został przedstawiony w skali logartymicznej.

\begin{figure}[ht!]
\centering
\includegraphics[scale = 0.33]{batcher.png}
\caption{Rozkład długości ścieżek w sieci Batchera sortującej bez modyfikacji, z komparatorem 1-bitowym}
\end{figure}

\subsubsection{Analiza długości ścieżek}
Maksymalna, średnia oraz minimalna długość ścieżki zmieniają się w zależności od liczby linii.
Należy zaobserwować zachowanie wykresu przy liczbie wejść - 2, 4, 16 i 32.

\begin{table}[ht!]
\begin{displaymath}
% use packages: array
\begin{tabular}{|l|l|l|l|l|}
\hline
liczba~wejść & najkrótsza & średnia~długość & najdłuższa \\
pierwotnych & ścieżka & ścieżki & ścieżka \\ \hline
2 & 2 & 2 & 2 \\ \hline
3 & 2 & 3 & 4 \\ \hline
4 & 3 & 3 & 4 \\ \hline
5 & 3 & 5 & 6 \\ \hline
6 & 3 & 5 & 7 \\ \hline
7 & 3 & 6 & 7 \\ \hline
8 & 4 & 6 & 7 \\ \hline
9 & 4 & 7 & 9 \\ \hline
... & ... & ... & ... \\ \hline
15 & 4 & 9 & 11 \\ \hline
16 & 5 & 10 & 11 \\ \hline
17 & 5 & 11 & 13 \\ \hline
... & ... & ... & ... \\ \hline
31 & 5 & 14 & 16 \\ \hline
32 & 6 & 14 & 16 \\ \hline
33 & 6 & 15 & 18 \\ \hline
\end{tabular}
\end{displaymath}
\caption{Zestawienie statystyki ścieżek w zależności od liczby wejść w sieci Batchera.}
\end{table} 

\begin{figure}[ht!]
\centering
\includegraphics[scale = 0.36]{dlugosc_sciezki_normal.png}
\caption{Wizualizacja zależności długości ścieżek od liczby wejść.}
\end{figure} 


\newpage
\subsection{Zmodyfikowana sieć sortująca nieparzysto-parzysta Batchera}
\label{sec:siec-zmodyfikowana}
Algorytm generowania sieci sortującej został zaimplementowany w następujący sposób:
\begin{itemize}
 \item dla potęg liczby 2, przeprowadzana jest redukcja i modyfikacja,
 \item dla innych rozmiarów przeprowadzona zostanie modyfikacja/redukcja, pod warunkiem że sieć scalająca będzie o parzystym rozmiarze.
\end{itemize}

\subsubsection{Analiza długości ścieżek}
Maksymalna, średnia oraz minimalna długość ścieżki zmieniają się w zależności od liczby linii.

\begin{table}[ht!]
\begin{displaymath}
% use packages: array
\begin{tabular}{|l|l|l|l|}
\hline
liczba~wejść & najkrótsza & średnia~długość & najdłuższa \\
pierwotnych & ścieżka & ścieżki & ścieżka \\ \hline
2 & 2 & 2 & 2 \\ \hline
3 & 2 & 3 & 4 \\ \hline
4 & 3 & 3 & 4 \\ \hline
5 & 3 & 5 & 6 \\ \hline
6 & 3 & 5 & 7 \\ \hline
7 & 3 & 6 & 7 \\ \hline
8 & 4 & 6 & 7 \\ \hline
9 & 4 & 7 & 9 \\ \hline
... & ... & ... & ...  \\ \hline
15 & 4 & 9 & 11 \\ \hline
16 & 5 & 9 & 12 \\ \hline
17 & 5 & 11 & 13 \\ \hline
... & ... & ... & ...  \\ \hline
31 & 5 & 14 & 17 \\ \hline
32 & 6 & 14 & 19 \\ \hline
\end{tabular}
\end{displaymath}
\caption{Zestawienie długości ścieżek w zależności od liczby linii w zmodyfikowanej sieci Batchera.}
\end{table} 

\begin{figure}[ht!]
\centering
%\includegraphics[scale = 0.42]{dlugosc_sciezek.png}
\includegraphics[scale = 0.36]{dlugosc_sciezki_modified.png}
\caption{Wizualizacja zależności długości ścieżek od liczby linii w zmodyfikowanej sieci Batchera.}
\end{figure}

\newpage
\subsubsection{Analiza ilości ścieżek}
Wykres pokazuje, że algorytm modyfikacji sieci Batchera, pozwala na drastyczne zmniejszenie ilości ścieżek, a co za tym idzie - zmniejszenie podatności na błędy typu opóźnienie ścieżki.

\begin{figure}[ht!]
\centering
%\includegraphics[scale = 0.40]{gates_and_connections.png}
\includegraphics[scale = 0.34]{liczba_sciezek.png}
\caption{Wizualizacja statystyki ilości ścieżek w zależności od liczby linii w zwykłej i zmodyfikowanej sieci Batchera.}
\end{figure}


\newpage
\subsection{Analiza sieci scalającej}
Sieć scalająca została zaimplementowana tylko dla liczb parzystych. Dotyczy to zarówno sieci z modyfikacją i redukcją, jak i bez.

\begin{figure}[ht!]
\centering
\includegraphics[scale = 0.36]{scalak_dlugosc.png}
\caption{Wizualizacja długości ścieżek w zależności od liczby wejść w zwykłej oraz zmodyfikowanej sieci scalającej.}
\end{figure}

\begin{figure}[ht!]
\centering
\includegraphics[scale = 0.34]{scalak_ilosc.png}
\caption{Wizualizacja ilosci ścieżek w zależności od liczby wejść w zwykłej oraz zmodyfikowanej sieci scalającej.}
\end{figure}

\newpage
\section{Obługa programu}
\label{sec:obsluga}
\subsection{Interfejs CLI}
Za pomocą programu stworzonego na potrzeby przeprowadzenia badań, możliwe jest zwykłe sortowanie podanych słów. Służy do tego prosty w obsłudze interfejs CLI. Uruchamia się go w następujący sposób:\\
\texttt{python ./generator.py Size Type Modify Reduction TestVector}\\
gdzie:
\begin{itemize}
	\item \texttt{Size} - Rozmiar układu (ilość sortowanych bitów).
	\item \texttt{Type} - Typ układu (\texttt{Merge}/\texttt{Sort}).
	\item \texttt{Modify} - Modyfikacja (\texttt{True}/\texttt{False}).
	\item \texttt{Reduction} - Modyfikacja z redukcją (\texttt{True}/\texttt{False}).
	\item \texttt{TestVector} - Wektor testowy o długości \texttt{Size} bądź \texttt{ALL} w celu zbadania wszystkich możliwości
\end{itemize}
Przykładowe wywołanie:\\
\texttt{python ./generator.py 4 Merge True True 1010}\\
Standardowe wyjście:
\begin{verbatim}
----------------------------------------------
Generating odd even merge circuit... size:4
Creating IO connections...
4 Input and 4 Output connections created
Creating odd-even circuit of size 4...
Comparator:1-2
Created and connected, 1 comparators used
Creating odd-even circuit of size 2...
Comparator:0-2
Created and connected, 1 comparators used
Odd-even circuit of size 1, we got inputs!
Odd-even circuit of size 1, we got inputs!
Creating odd-even circuit of size 2...
Comparator:1-3
Created and connected, 1 comparators used
Odd-even circuit of size 1, we got inputs!
Odd-even circuit of size 1, we got inputs!
Connecting inputs to created structure...
Reducing unnecessary connections...
Removed 14 connections
Reducing unnecessary MultiOutputs...
Removed 2 MultiOutputs
Finished! 10 gates, 14 connections, 4*2 IO connections and 3 comparators
----------------------------------------------
----------------------------------------------
Find shortcuts
Line 1 level max: 1 lastUpLevel: -1
Line 2 level max: 1 lastDownLevel: -1
First half modification
Line: 1: full reduction, skiping modify
Second half modification
Line: 2: full reduction, skiping modify
Removed 0 connections
Removed 0 MultiOutputs
----------------------------------------------
Output:[True, True, False, False]
\end{verbatim}
Po uruchomieniu programu następuje generacja układu i otrzymujemy wynik działania wygenerowanego układu dla zadanego wektora (ostatnia linia).

\subsection{Analizator}
Obsługa programu analizatora układu jest łatwa. Podczas wywyłania, należy obligatoryjnie podać trzy parametry.\\
\texttt{./analyzer.py  -size n -modify 0/1 -reduce 0/1}\\
Uwaga! Dla dużego rozmiaru \texttt{n}, program działa długo.


\newpage
\section{Uwagi końcowe}
\label{sec:uwagi-koncowe}
Dziękujemy dr Piotrowi Patronikowi za wsparcie merytoryczne i ``duchowe'', przy opracowywaniu niniejszej dokumentacji oraz projektu.\\
Oprogramowanie które służyło badaniom, dostępne jest na licencji GPL2 pod adresem\\ \texttt{http://code.google.com/p/batcher-analyzer}.\\
Najnowszą wersję można pobrać z repozytorium SVN, poleceniem\\ \texttt{svn checkout http://batcher-analyzer.googlecode.com/svn/trunk/ \\\ batcher-analyzer-read-only}.


\newpage
\begin{thebibliography}{99}
\addcontentsline{toc}{section}{Bibliografia}
%\bibitem{PYTDOC} \emph{Dokumentacja do języka Python 2.5 (http://python.org)}.
\bibitem{PATRONIK} P. Patronik, \emph{``Metody syntezy układów realizujących funkcje symetryczne i progowe testowalnych dla uszkodzeń typu opóźnienia''}, praca doktorska, Wrocław 2006. \label{bib_patronik}
\bibitem{SURMACZ} T. Surmacz, \emph{``Metody generowania minimalnego zbioru testów dla pewnych klas sieci sortujących''}, praca doktorska, Wrocław, 2004.
\bibitem{CORMEN} T. Cormen, \emph{Wprowadzenie do algorytmów}.
\bibitem{LANG} H.W. Lang, \emph{``Odd-even mergesort''}, online, Germany, 1998.\\http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm
\bibitem{BATCHER} K.E. Batcher, \emph{``Sorting Networks and their Applications''}, AFIPS Spring Joint Comput. Conf., 1968.

\end{thebibliography}

\end{document}

